package zw_601_700.zw_680_验证回文串II;

class Solution {

    public static void main(String[] args) {
        String s = "abca";
        boolean b = validPalindrome(s);
        System.out.println(b);
    }


    /**
     * 先判断字符串首尾是否相等，如果是，则首尾同时往中间移动一个字符，继续判断
     * 如果不是，首往中间移动一个字符，或者尾往中间移动一个字符，继续判断
     *      如果不是直接返回结果，
     *      如果是，首位同时往中间移动一位，继续判断
     * 返回最终结果。
     *
     * @param s
     * @return
     */
    public static boolean validPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        char[] chars = s.toCharArray();
        while (i < j && chars[i] == chars[j]) {
            i++;
            j--;
        }
        // 至此有两种情况：
        // ① i>=j s本身就是回文串
        // ② i<j && s[i] != s[j]必须要删一个
        //   要么删s[i]，判断s[i+1,j]是否是回文串
        //   要么删s[j]，判断s[i,j-1]是否是回文串
        return i >= j
                || isPalindrome(chars, i + 1, j)
                || isPalindrome(chars, i, j - 1);
    }

    private static boolean isPalindrome(char[] chars, int i, int j) {
        while (i < j && chars[i] == chars[j]) {
            i++;
            j--;
        }
        return i >= j;
    }


    /**
     * 递归
     *
     * @param s
     * @return
     */
//    public static boolean validPalindrome(String s) {
//        return checkDel(s, 0, s.length() - 1, true);
//    }
//
//    private static boolean checkDel(String s, int i, int j, boolean canDel) {
//        while (i < j && s.charAt(i) == s.charAt(j)) {
//            ++i;
//            --j;
//        }
//        if (i >= j) return true;
//        return canDel && (checkDel(s, i, j - 1, false) || checkDel(s, i + 1, j, false));
//    }
}
